# **************************************
# --*-- coding: utf-8 --*--
# @Author  : white
# @FileName: KNN兔子.py
# @Time    : 2025-08-14
# **************************************

"""
在这些数据中，(身高,体重)的二元组叫做特征（features），
兔子的品种则是分类标签（class label）。
我们想解决的问题是，给定一个未知分类的新样本的所有特征，通过已知数据来判断它的类别。

那么现在有一迷之兔子，我们想判断它的类别，要怎么做呢？
按照最普通的直觉，应该在已知数据里找出几个和我们想探究的兔子最相似的几个点，
然后看看那些兔子都是什么个情况；如果它们当中大多数都属于某一类别，那么迷之兔子大概率也就是那个类别了。
于是乎，我们给机器人预设一个整数 k，让它去寻找距离最近的k个数据样本进行分析。

可我们的机器才识别不了那么多，它只测量出这只兔子身长40厘米，体重 2.7公斤，图中那颗闪闪发亮的红星

kNN 算法如何对这次观测进行分类要取决于k的大小。
直觉告诉我们迷之兔像是一只绝望，因为除了最近的蓝色三角外，附近其他都是黄色圆圈。
的确，如果设k=15，算法会判断这只兔子是一只绝望。但是如果设k=1，
那么由于距离最近的是蓝色三角，会判断迷之兔子是一只痛苦。

如果按照15NN和1NN的方法对这个二维空间上的每一个点进行分类
在两组分类中，1NN 的分类边界明显更“崎岖”，但是对历史样本没有误判；
而 15NN 的分类边界更平滑，但是对历史样本有发生误判的现象。
选择k的大小取决于对偏差和方差之间的权衡，
本篇不进行更深探讨，读者在使用 kNN 时凭感觉选一个k就好。

距离函数
我们在上面的例子中把一个很重要的概念隐藏了起来，在
选择一个数量k还只是小问题，更重要的是距离的计算方法。毕竟，当我们说“最近的k个点”时，这个“近”是怎么衡量的？

是！注意！使用 kNN 时需要根据特征数据的取值区间来调整坐标轴的比例，这个做法叫作标准化或者归一化。
为什么要这么做呢？拿上面的例子来说，一只兔子的身长（cm）数值平均是它的体重（kg）的10倍左右，
如果我们在这组数值上直接使用L2距离函数的话就会导致横轴的距离比重明显放大，分类结果也不合理

如果把坐标轴成其他的单位，比如毫米和吨，并用相应的新数值来计算距离，又会得到完全不同的分类标准。
甚至，在极端情况下，如果身高用纳米并且体重用吨计量，那么相比之下身高的数值会奇高无比，
以至于两点之间的距离是完全由身高决定的，体重则没有任何权重。
为了解决这个问题，我们应该在计算距离时把所有坐标轴进行归一化。

概率 kNN
上面的kNN算法返回的是对一组特征的绝对分类，告诉我们这只兔子被判断为哪一个类别。
可有时我们并不想知道一个确切地分类，而想知道它属于某个分类的概率是多大。
比如我们发现一只身长 373737体重4.8的小兔兔，在下图五角星的位置。

这只兔子的特征数据在悲伤和痛苦的分界处，机器不论判断它属于哪个类别都很有可能是错的。
这时，类似“它有一半可能性是痛苦，一半可能性是悲伤”的反馈会更有意义。

为了这个目的，我们同样找找出距离问题特征最近的 k个样本，但与其寻找数量最多的分类，
我们统计其中每个类别的分别有多少个，再除以 k得到一个属于每一个类别概率值。比如在上面的图里，
距离五角星最近的 15个样本中，有 8只悲伤和 7只痛苦，
由此判断：它有 53%的可能性是悲伤，47%的可能性是痛苦，0%的可能性是绝望。
在整个二维空间中的每一个点上进行概率 kNN 算法，
可以得到每个特征点是属于某个类别的概率热力图，图中颜色越深代表概率越大。

比如说，我们知道悲伤兔子喜欢向我们的机器人上喷洒奇怪的粘液，毫无作用毫无意义的绿色的粘液，
倒不是因为别的，我们就是觉得这种粘液很恶心，清洗起来也很麻烦，所以我们想让机器人在测量并发现是悲伤之后马上掉头逃跑。
但是如果机器发现了一只体型接近痛苦的悲伤，并且普通的 kNN 算法发生误判，没有马上逃跑，那么最后就会被喷了。
所以我们使用概率 kNN 的算法并且使用以下风控原则：只要发现兔子有30%以上的概率是悲伤，就马上逃跑。从此之后，机器人就再也没被喷过。

不知你有没有发现，我跟你讲了这么多关于兔子的事，却丝毫没有提及如何用代码计算 kNN。
这是因为 kNN 虽然思路简单，但实现起来有一个问题，那就是计算量很大；
当数据量很多时，拿一组特征来和所有样本依次计算距离并选取最近的k个，是非常耗费时间的。
所以，在量化课堂接下来的文章中，我们将讲解 kNN 的一个高效算法KD树。
"""
import random
import operator
import datetime
import numpy as np
import pandas as pd
import statsmodels.api as sm
import matplotlib.pyplot as plt
from join_quant.libs import KDTree, normalized_dist, draw_scatter
from pathlib import Path

img = Path("images")
img.mkdir(exist_ok=True)
plt.rcParams['font.family'] = 'SimHei'

point_x, point_y = 40, 2.7

# 100个正态分布的 悲伤
grief_heights = np.random.normal(50, 6, 100)
grief_weights = np.random.normal(5, 0.5, 100)

# 100个正态分布的 痛苦
agony_heights = np.random.normal(30, 6, 100)
agony_weights = np.random.normal(4, 0.5, 100)

# 100个正态分布的 绝望
despair_heights = np.random.normal(45, 6, 100)
despair_weights = np.random.normal(2.5, 0.5, 100)

all_sample = {
    "grief_heights"  : grief_heights,
    "grief_weights"  : grief_weights,
    "agony_heights"  : agony_heights,
    "agony_weights"  : agony_weights,
    "despair_heights": despair_heights,
    "despair_weights": despair_weights
}

# 设置图片大小
fig_size = plt.rcParams["figure.figsize"]
fig_size[0] = 15
fig_size[1] = 10

draw_scatter(img=img, title="原始分布图.png",
             point_x=point_x, point_y=point_y, **all_sample)

# 设置样本集 ((身高,体重),类别) 前者为特征，后者为标签
grieves = map(lambda x, y: tuple(((x, y), 'g')), grief_heights, grief_weights)
agonies = map(lambda u, v: tuple(((u, v), 'b')), agony_heights, agony_weights)
despairs = map(lambda a, b: tuple(((a, b), 'y')), despair_heights, despair_weights)
_d = list(grieves) + list(agonies) + list(despairs)
# 创建最顶层KD数
tree = KDTree(_d)

# 穷举生成空间上的点
all_points = []
for i in range(100, 701):
    for j in range(100, 701):
        all_points.append((float(i) / 10., float(j) / 100.))

############### 每个点运算 15NN，并记录计算时间 ###############
now = datetime.datetime.now()
fifteen_NN_result = []
for point in all_points:
    # 将当前点属于哪个分类结果进行储存
    fifteen_NN_result.append((point, tree.knn(point, k=15, dist=normalized_dist)[0]))
print("每个点运算 15NN耗时：", datetime.datetime.now() - now)

draw_scatter(img=img, title="15NN分类.png", class_result=fifteen_NN_result,
             point_x=point_x, point_y=point_y, **all_sample)

############### 每个点运算 1NN，并记录计算时间 ###############
now = datetime.datetime.now()
one_NN_result = []
for point in all_points:
    one_NN_result.append((point, tree.knn(point, k=1, dist=normalized_dist)[0]))
print("每个点运算 1NN耗时：", datetime.datetime.now() - now)

draw_scatter(img=img, title="1NN分类.png", class_result=one_NN_result,
             point_x=point_x, point_y=point_y, **all_sample)
############### 使用未归一化的距离计算 15NN ###############
now = datetime.datetime.now()
bad_NN_result = []
for point in all_points:
    bad_NN_result.append((point, tree.knn(point, k=15)[0]))
print("使用未归一化的距离计算 15NN耗时：", datetime.datetime.now() - now)
draw_scatter(img=img, title="15NN距离未归一化.png", class_result=bad_NN_result,
             point_x=point_x, point_y=point_y, **all_sample)

############### 15NN 计算是悲伤的概率 ###############
now = datetime.datetime.now()
grief_prob = []
for point in all_points:
    grief_prob.append((point, tree.knn_prob(point, label='g', k=15, dist=normalized_dist)))
print("15NN 计算是悲伤的概率耗时：", datetime.datetime.now() - now)
draw_scatter(img=img, title="15NN悲伤的概率.png", class_result=grief_prob,
             point_x=point_x, point_y=point_y, **all_sample)

############### 15NN计算是痛苦的概率 ###############
now = datetime.datetime.now()
agony_prob = []
for point in all_points:
    agony_prob.append((point, tree.knn_prob(point, label='b', k=15, dist=normalized_dist)))
print("15NN计算是痛苦的概率耗时：", datetime.datetime.now() - now)
draw_scatter(img=img, title="15NN痛苦的概率.png", class_result=agony_prob,
             point_x=point_x, point_y=point_y, **all_sample)

############### 15NN 计算是绝望的概率 ###############
now = datetime.datetime.now()
despair_prob = []
for point in all_points:
    despair_prob.append((point, tree.knn_prob(point, label='y', k=15, dist=normalized_dist)))
print("15NN 计算是绝望的概率耗时", datetime.datetime.now() - now)
draw_scatter(img=img, title="15NN绝望的概率.png", class_result=despair_prob,
             point_x=point_x, point_y=point_y, **all_sample)
